/*-------------------------------------------------------------------------
 *
 * levenshtein.c
 *	  Levenshtein distance implementation.
 *
 * Original author:  Joe Conway <mail@joeconway.com>
 *
 * This file is included by varlena.c twice, to provide matching code for (1)
 * Levenshtein distance with custom costings, and (2) Levenshtein distance with
 * custom costings and a "max" value above which exact distances are not
 * interesting.  Before the inclusion, we rely on the presence of the inline
 * function rest_of_char_same().
 *
 * Written based on a description of the algorithm by Michael Gilleland found
 * at http://www.merriampark.com/ld.htm.  Also looked at levenshtein.c in the
 * PHP 4.0.6 distribution for inspiration.  Configurable penalty costs
 * extension is introduced by Volkan YAZICI <volkan.yazici@gmail.com.
 *
 * Copyright (c) 2001-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	src/backend/utils/adt/levenshtein.c
 *
 *-------------------------------------------------------------------------
 */
#define MAX_LEVENSHTEIN_STRLEN		255

/*
 * 计算提供字符串之间的 Levenshtein 距离度量，这些字符串
 * 不一定以 null 结尾。
 *
 * source: 源字符串，长度为 slen 字节。
 * target: 目标字符串，长度为 tlen 字节。
 * ins_c, del_c, sub_c: 对于字符插入、删除和替代分别收取的费用；
 * (1, 1, 1) 的费用足以应对常见情况，但您的情况可能会有所不同。
 * max_d: 如果提供并且 >= 0，最大我们关心的距离；见下文。
 * trusted: 调用者是可信的，无需遵守 MAX_LEVENSHTEIN_STRLEN。
 *
 * 计算 Levenshtein 距离的一种方法是逐步构建
 * 一个 (m+1)x(n+1) 矩阵，其中单元格 (i, j) 表示将 s 的前 i 个字符
 * 转换为 t 的前 j 个字符所需的最小操作数。最后一行的最后一列是
 * 答案。
 *
 * 我们在这里使用该算法，并进行了一些修改。为了不一次性在内存中
 * 保留整个数组，我们只使用两个大小为 m+1 的数组来存储累积值。
 * 在每一步，一个数组代表“前一”行，另一个是“当前”行，
 * 假设的巨大数组。
 *
 * 如果 max_d >= 0，我们只需在答案小于或等于 max_d 时提供准确答案。
 * 从矩阵中的任何单元开始，该单元与最后一行的最后一列之间存在理论上的
 * “最小剩余距离”。当字符串未转换的部分长度相等时，这个最小剩余距离为零
 * （因为我们可能会幸运地找到所有剩余字符匹配），否则基于所需的最小
 * 插入或删除次数来使它们相等。当我们向上右或下左角移动矩阵时，剩余距离
 * 增长。当 max_d 界限恰好合适时，我们可以利用这个属性避免计算每行的全部内容；
 * 相反，我们维护一个 start_column 和 stop_column，标识离对角线较近的矩阵部分，
 * 其仍然可以影响最终答案。
 */
int
#ifdef LEVENSHTEIN_LESS_EQUAL
varstr_levenshtein_less_equal(const char *source, int slen,
							  const char *target, int tlen,
							  int ins_c, int del_c, int sub_c,
							  int max_d, bool trusted)
#else
varstr_levenshtein(const char *source, int slen,
				   const char *target, int tlen,
				   int ins_c, int del_c, int sub_c,
				   bool trusted)
#endif
{
	int			m,
				n;
	int		   *prev;
	int		   *curr;
	int		   *s_char_len = NULL;
	int			i,
				j;
	const char *y;

	/*
	 * 对于 varstr_levenshtein_less_equal，我们有真实变量
	 * start_column 和 stop_column；否则，它只是在 0 和
	 * m 之间的简写。
	 */
#ifdef LEVENSHTEIN_LESS_EQUAL
	int			start_column,
				stop_column;

#undef START_COLUMN
#undef STOP_COLUMN
#define START_COLUMN start_column
#define STOP_COLUMN stop_column
#else
#undef START_COLUMN
#undef STOP_COLUMN
#define START_COLUMN 0
#define STOP_COLUMN m
#endif

	/* 将字符串长度（以字节为单位）转换为字符长度 */
	m = pg_mbstrlen_with_len(source, slen);
	n = pg_mbstrlen_with_len(target, tlen);

	/*
	 * 我们可以通过 n 次插入将空字符串 s 转换为 t，或通过 m 次删除
	 * 将非空 t 转换为空字符串 s。
	 */
	if (!m)
		return n * ins_c;
	if (!n)
		return m * del_c;

	/*
	 * 出于安全考虑，限制过度的 CPU+RAM 使用。（此
	 * 实现使用 O(m) 内存，复杂度为 O(mn)。）如果
	 * “trusted”为 true，调用者负责不进行过度请求，
	 * 通常通过使用小的 max_d 以及长度有限的字符串，
	 * 尽管不一定精确到 MAX_LEVENSHTEIN_STRLEN。
	 */
	if (!trusted &&
		(m > MAX_LEVENSHTEIN_STRLEN ||
		 n > MAX_LEVENSHTEIN_STRLEN))
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
				 errmsg("levenshtein argument exceeds maximum length of %d characters",
						MAX_LEVENSHTEIN_STRLEN)));

#ifdef LEVENSHTEIN_LESS_EQUAL
	/* 初始化起始和停止列。 */
	start_column = 0;
	stop_column = m + 1;

	/*
	 * 如果 max_d >= 0，确定该界限是否不可能过于紧。 如果是，
	 * 立即返回 max_d + 1。否则，确定它是否足够紧以限制
	 * 我们必须进行的计算。如果是，则找出初始停止列。
	 */
	if (max_d >= 0)
	{
		int			min_theo_d; /* 理论上的最小距离。 */
		int			max_theo_d; /* 理论上的最大距离。 */
		int			net_inserts = n - m;

		min_theo_d = net_inserts < 0 ?
			-net_inserts * del_c : net_inserts * ins_c;
		if (min_theo_d > max_d)
			return max_d + 1;
		if (ins_c + del_c < sub_c)
			sub_c = ins_c + del_c;
		max_theo_d = min_theo_d + sub_c * Min(m, n);
		if (max_d >= max_theo_d)
			max_d = -1;
		else if (ins_c + del_c > 0)
		{
			/*
			 * 计算应填充的名义矩阵第一行的数量。如果字符串正在增长，理论上的最小距离已经包含了将两个字符串长度相等所需删除字符的成本。每增加一次删除，就会强制进行一次插入，因此最佳情况的总成本增加了 ins_c + del_c。如果字符串正在缩减，最小的理论成本假设没有多余的删除；也就是说，我们不会比列 n - m 右边更开始。如果我们确实是从右侧更远开始，最佳情况的总成本会因每次向右移动而增加 ins_c + del_c。*/
			int			slack_d = max_d - min_theo_d;
			int			best_column = net_inserts < 0 ? -net_inserts : 0;

			stop_column = best_column + (slack_d / (ins_c + del_c)) + 1;
			if (stop_column > m)
				stop_column = m + 1;
		}
	}
#endif

	/*
	 * 为了避免在 s 的每个字符上重复调用 pg_mblen()，我们在开始主循环之前缓存所有长度——但如果两个字符串中的所有字符都是单字节的，那么我们跳过此步骤，在主循环中使用快速路径。如果只有一个字符串包含多字节字符，我们仍然构建数组，以便快速路径不必处理数组未初始化的情况。*/
	if (m != slen || n != tlen)
	{
		int			i;
		const char *cp = source;

		s_char_len = (int *) palloc((m + 1) * sizeof(int));
		for (i = 0; i < m; ++i)
		{
			s_char_len[i] = pg_mblen(cp);
			cp += s_char_len[i];
		}
		s_char_len[i] = 0;
	}

	/* 初始化列和行需要一个额外的单元。 */
	++m;
	++n;

	/* 名义数组的前一行和当前行。 */
	prev = (int *) palloc(2 * m * sizeof(int));
	curr = prev + m;

	/*
	 * 要将 s 的前 i 个字符转换为 t 的前 0 个字符，我们必须执行 i 次删除。*/
	for (i = START_COLUMN; i < STOP_COLUMN; i++)
		prev[i] = i * del_c;

	/* 遍历名义数组的行 */
	for (y = target, j = 1; j < n; j++)
	{
		int		   *temp;
		const char *x = source;
		int			y_char_len = n != tlen + 1 ? pg_mblen(y) : 1;

#ifdef LEVENSHTEIN_LESS_EQUAL

		/*
		 * 在最佳情况下，值沿对角线向下过滤不变，因此我们必须递增 stop_column，除非它已经处于数组的右端。内部循环将读取 prev[stop_column]，因此我们必须初始化它，即使它不应该影响结果。*/
		if (stop_column < m)
		{
			prev[stop_column] = max_d + 1;
			++stop_column;
		}

		/*
		 * 主循环填充 curr，但 curr[0] 需要一个特例：要将 s 的前 0 个字符转换为 t 的前 j 个字符，我们必须执行 j 次插入。不过，如果 start_column > 0，这个特例不适用。*/
		if (start_column == 0)
		{
			curr[0] = j * ins_c;
			i = 1;
		}
		else
			i = start_column;
#else
		curr[0] = j * ins_c;
		i = 1;
#endif

		/*
		 * 这个内部循环对性能至关重要，因此我们包括一个快速路径来处理（相当普遍的）没有多字节字符的情况。快速路径有权假设，如果 s_char_len 没有初始化，那么两个字符串都只包含单字节字符。*/
		if (s_char_len != NULL)
		{
			for (; i < STOP_COLUMN; i++)
			{
				int			ins;
				int			del;
				int			sub;
				int			x_char_len = s_char_len[i - 1];

				/*
				 * 计算插入、删除和替换的成本。
				 *
				 * 在计算替换的成本时，我们首先比较每个可能的多字节字符的最后一个字符，因为这足以排除大多数不匹配。如果我们通过了该测试，那么我们将比较长度和剩余字节。*/
				ins = prev[i] + ins_c;
				del = curr[i - 1] + del_c;
				if (x[x_char_len - 1] == y[y_char_len - 1]
					&& x_char_len == y_char_len &&
					(x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
					sub = prev[i - 1];
				else
					sub = prev[i - 1] + sub_c;

				/* 选择成本最低的。 */
				curr[i] = Min(ins, del);
				curr[i] = Min(curr[i], sub);

				/* 指向下一个字符。 */
				x += x_char_len;
			}
		}
		else
		{
			for (; i < STOP_COLUMN; i++)
			{
				int			ins;
				int			del;
				int			sub;

				/* 计算插入、删除和替换的成本。 */
				ins = prev[i] + ins_c;
				del = curr[i - 1] + del_c;
				sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c);

				/* 选择成本最低的。 */
				curr[i] = Min(ins, del);
				curr[i] = Min(curr[i], sub);

				/* 指向下一个字符。 */
				x++;
			}
		}

		/* 交换当前行和前一行。 */
		temp = curr;
		curr = prev;
		prev = temp;

		/* 指向下一个字符。 */
		y += y_char_len;

#ifdef LEVENSHTEIN_LESS_EQUAL

		/*
		 * 如果在没有 max_d 限制的情况下使用这一段代码，则会显著影响性能。这可能并不是因为 max_d >= 0 的测试本身很昂贵，而是因为可能需要执行这段代码阻碍了循环整体的紧凑优化。*/
		if (max_d >= 0)
		{
			/*
			 * “零点”是当前行的列，其中字符串的剩余部分长度相等。目标字符串中有 (n - 1) 个字符，其中 j 已被转换。源字符串中有 (m - 1) 个字符，因此我们想要找到 zp 的值，其中 (n - 1) - j = (m - 1) - zp。*/
			int			zp = j - (n - m);

			/* 检查停止列是否可以向左滑动。 */
			while (stop_column > 0)
			{
				int			ii = stop_column - 1;
				int			net_inserts = ii - zp;

				if (prev[ii] + (net_inserts > 0 ? net_inserts * ins_c :
								-net_inserts * del_c) <= max_d)
					break;
				stop_column--;
			}

			/* 检查起始列是否可以向右滑动。 */
			while (start_column < stop_column)
			{
				int			net_inserts = start_column - zp;

				if (prev[start_column] +
					(net_inserts > 0 ? net_inserts * ins_c :
					 -net_inserts * del_c) <= max_d)
					break;

				/*
				 * 我们将不再更新这些值，因此必须确保这里没有可能导致将来外部循环迭代混乱的内容。*/
				prev[start_column] = max_d + 1;
				curr[start_column] = max_d + 1;
				if (start_column != 0)
					source += (s_char_len != NULL) ? s_char_len[start_column - 1] : 1;
				start_column++;
			}

			/* 如果它们交叉，我们将超出边界。 */
			if (start_column >= stop_column)
				return max_d + 1;
		}
#endif
	}

	/*
	 * 因为最终值是从前一行交换到当前行的，所以我们将在这里找到它。*/
	return prev[m - 1];
}
